package com.zdp.algorithm.od;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author ZhengDp
 * @Date 2023/6/7 22:26
 */
public class 阿里巴巴找宝箱IV {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()) {
            List<Integer> list = Arrays.stream(in.nextLine().split(","))
                    .map(Integer::valueOf).collect(Collectors.toList());
            System.out.println("method1 ===");
            String res1 = method1(list).stream().map(String::valueOf).collect(Collectors.joining(","));
            System.out.println(res1);
            System.out.println("method2 ===");
            String res2 = method2(list).stream().map(String::valueOf).collect(Collectors.joining(","));
            System.out.println(res2);
            System.out.println(res1.equals(res2));
        }
    }

    private static List<Integer> method2 (List<Integer> list ) {
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> res = new ArrayList<>(list.size());
        // 存放坐标
        Deque<Integer> queue = new LinkedList<>();
        for(int i =0;i<list.size();i++) {
            int curNum = list.get(i);
            while(!queue.isEmpty() && curNum > list.get(queue.getLast())) {
                int minIndex = queue.removeLast();
                map.put(minIndex,curNum);
            }
            queue.addLast(i);
        }
        int i =0;
        while(i<list.size() && !queue.isEmpty()) {
            if(i == queue.getLast()) {
                while(!queue.isEmpty()) {
                    map.put(queue.removeLast(),-1);
                }
            } else if(list.get(i) > list.get(queue.getLast())) {
                map.put(queue.removeLast(),list.get(i));
            } else {
                i++;
            }
        }
        for(i =0;i<list.size();i++) {
            res.add(map.get(i));
        }
        return res;
    }

    private static List<Integer> method1(List<Integer> list) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i<list.size();i++) {
            int j =(i+1)%list.size();
            while(i != j) {
                if(list.get(j) > list.get(i)) {
                    res.add(list.get(j));
                    break;
                } else {
                    j = (j+1) % list.size();
                }
            }
            if(i == j) {
                res.add(-1);
            }
        }
        return res;
    }
}
